package pers.qianyu.month_202012.date_20201220;

/**
 * 793. 阶乘函数后K个零
 * https://leetcode-cn.com/problems/preimage-size-of-factorial-zeroes-function/
 *
 * @author mizzle rain
 * @date 2020-12-20 21:20
 */
public class PreimageSizeFZF {
    public int preimageSizeFZF(int K) {
        return (int) (findRight(K) - findLeft(K) + 1);
    }

    private long findRight(int k) {
        long left = 0, right = Long.MAX_VALUE;
        while (left <= right) {
            long mid = left + ((right - left) >> 1);
            if (trailingZeroes(mid) <= k) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }

    private long findLeft(int k) {
        long left = 0, right = Long.MAX_VALUE;
        while (left <= right) {
            long mid = left + ((right - left) >> 1);
            if (trailingZeroes(mid) >= k) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }


    public long trailingZeroes(long n) {
        long count = 0;
        long d = 5;
        while (n >= d) {
            count += n / d;
            d *= 5;
        }
        return count;
    }
}
